Modular Arithmetic

Modular arithmetic is concerned with the arithmetic of remainders from division.

Modulo Reduction

Dividing $a$ by $N$ can be written as $a = Nq + r$ , where $q$ is the quotient and $r$ is the remainder. The modulo operation (%) returns the remainder $r$ when dividing $a$ by $N$ . Programmatically, this is written as a % N and the mathematical equivalent is $a mod N$ .

Mapping an integer $a$ to its remainder upon division by some number $N$ is known as reduction modulo $N$ and boils down to mapping the integer $a$ to an integer between $0$ and $N - 1$ .

Modulo Congruence

Two numbers are said to be congruent modulo $N$ , written as $a = b mod N$ (terrific notation, mathematicians) if they have the same remainder when dividing by $N$ , i.e. $[a mod N] = [b mod N]$ . The good thing about modulo congruence is that it under addition, subtraction and multiplication:

${a = a^{'} mod N b = b^{'} mod N ⟺ {(a \pm b) = (a^{'} \pm b^{'}) mod N ab = a^{'} b^{'} mod N$

Modulo Inversion

If there is an integer $c$ such that $b c = 1 mod N$ , then $b$ is said to be invertible modulo $N$ and $c$ is said to be a (multiplicative) inverse of $b$ modulo $N$ . A given integer $b$ may have many multiplicative inverses - for example, it is fairly easy to show that if $c$ is a multiplicative inverse of $b$ , then so is $c mod N$ and if $c^{'}$ is yet another inverse of $b$ , then $[c mod N] = [c^{'} mod N]$ . For simplicity, the multiplicative inverse of $b$ which is in the range ${0, 1, ..., N - 1}$ is denoted by $b^{- 1}$ .

Modulo division by $b$ can then be defined as multiplication by $b^{- 1}$ and this gives the following nice property:

$ab = c b mod N ⟹ (ab) b^{- 1} = (c b) b^{- 1} mod N ⟹ a = c mod N$

Groups

A group is simply a set $G$ equipped with a group operation $\circ$ which satisfy the following properties:

Closure: For all $g, h \in G$ , $g \circ h \in G$
Identity: There exists an identity element $e \in G$ such that for all $g \in G, g \circ e = g = e \circ g$
Invertibility: For each $g \in G$ there exists an inverse element $h \in G$ such that $g \circ h = e = h \circ g$
Associativity: For all $g_{1}, g_{2}, g_{3} \in G, (g_{1} \circ g_{2}) \circ g_{3} = g_{1} (\circ g_{2} \circ g_{3})$

A group whose operation also supports commutativity (i.e., $g \circ h = h \circ g$ ) is called abelian.

The order of a group, denoted by $∣ G ∣$ , is the number of elements in the group.

Additive vs Multiplicative Notation

The group operation $\circ$ is often denoted in a different way.

Additive notation uses the $+$ sign for its group operation, i.e. $g \circ h \equiv g + h$ . However, this does not mean that the group's operation is necessarily addition. The identity element here is denoted by $0$ and the inverse of an element $g$ is written as $- g$ . Applying the group operation to a single element $g$ a total of $m$ times is denoted as

$m g = m times g + g + \dots + g$

Note that $m$ is an integer while $g$ is an element of the group and so $m g$ is not the group operation applied between $m$ and $g$ .

Multiplicative notation denotes the group operation either by $g \cdot h$ or by $g h$ . Once again, this does not mean that the group operation is necessarily multiplication - it is simply written this way. The identity element here is denoted by $1$ and the inverse of an element $g$ is written as $g^{- 1}$ . Applying the group operation to a single element $g$ a total of $m$ times is denoted via exponentiation:

$g^{m} = m times g \dots g$

Once again, $m$ is an integer and not a member of the group. This is useful notation because it truly "behaves" like exponentiation in regards to its properties: $g^{m} \cdot g^{n} = g^{m + n}, (g^{m})^{n} = g^{mn}$ and $g^{1} = g$ . Furthermore, if the group $G$ is abelian, then for all $g, h \in G$ it holds that $g^{m} \cdot h^{m} = (g h)^{m}$ .

Some Facts about Groups

Lemma: Cancelation Law for Group Operations

For all $a, b, c \in G$ , if $a \circ c = b \circ c$ , then $a = b$ and in particular, if $a c = c$ , then $a$ is the identity element of $G$ .

Proof

TODO

Interestingly, if the group is finite and $m = ∣ G ∣$ , applying the group operation a single element $m$ number of times, then we get the identity element.

Theorem

For any finite group $G$ and element $g \in G$ , it holds that g^{|\mathbb{G}|} = 1.

Proof

TODO

As a corollary of this, it turns out that applying the group operation to the same element more than |\mathbb{G}| $t im es ha s t h es am ee ff ec t a s d o in g i t$ \mod |\mathbb{G}| times which brings computational benefits.

Theorem

For any finite group \mathbb{G} $w i t h$ |\mathbb{G}| \gt 1 $an d an y$ g \in \mathbb{G} $, i t h o l d s t ha t$ g^x = g^{[x \mod |\mathbb{G}|]}

Proof

The Groups \mathbb{Z}_N $an d$ \mathbb{Z}_N^ $T h e ab e l ian g ro u p$ \mathbb{Z}_N $d e n o t es t h ese t o f in t e g ers$ {0,1, ..., N - 1} $e q u i pp e d w i t ha dd i t i o nm o d u l o$ N $a s i t s g ro u p o p er a t i o n . T h ec l os u re p ro p er t y i s t r i v ia ll ys a t i s f i e d b ec a u se m o d u l ore d u c t i o n p ro d u ces an u mb er in t h er an g e$ {0,...,N_1} $. S imi l a r l y, a ssoc ia t i v i t y an d co mm u t a t i v i t y f o ll o w f ro m t h e f a c tt ha t in t e g ers ha v e t h ese p ro p er t i es . T h e i d e n t i t ye l e m e n t i s$ 0 $. S in ce$ a + (N - a) = 0 \mod N $, i t f o ll o w s t ha tt h e in v erseo f an ye l e m e n t i s$ N - a $. W e w o u l d l ik e t o ha v e a s imi l a r g ro u p b u tw i t hm u lt i pl i c a t i o nm o d u l o$ N $a s t h e g ro u p o p er a t i o n . Ho w e v er, t hi s i s n o tt r i v ia lt o d o b ec a u see v e nn o n - zeroe l e m e n t s in$ {0,1,..., N -1} $mi g h tl a c kanin v erse . I tt u r n so u tt ha tt h ee l e m e n t s in$ {0,1,..., N -1} $w hi c h * a re * in v er t ib l e m o d u l o$ N $a re p rec i se l y t h ose in t e g ers w hi c ha rere l a t i v e l y p r im e w i t h$ N $. T h ere f ore, w ec an d e f in e t h ese t f or$ \mathbb{Z}_N^ $a s f o ll o w s :$ $Z_{N}^{} : = {b \in {1, 2, ..., N - 1} ∣ g cd (b, N) = 1}$ $W ee q u i pt hi sse tw i t h t h eo p er a t i o nm u lt i pl i c a t i o nm o d u l o$ N $t oy i e l d t h e ab e l ian g ro u p$ \mathbb{Z}_N^.

Cyclic Groups

For any g \in \mathbb{G} $, w h ere$ \mathbb{G} $i sso m e f ini t e g ro u p, co n s i d er t h e f o ll o w in g se t :$ $⟨ g ⟩ : = {g^{0}, g^{1}, g^{2}, ...}$ $W e kn o w f ors u re t ha t$ g^{|\mathbb{G}|} = 1 $. L e t$ i\le |\mathbb{G}| $b e t h es ma ll es tp os i t i v e in t e g ers u c h t ha t$ g^i = 1 $. W e kn o wt h e n t ha tt h ese q u e n ce$ {g^0, g^1, g^2, ...} $re p e a t se v ery$ i $e l e m e n t s, i . e .$ g^i = g^0, g^{i+1} = g^1 $, e t c . T h ere f ore,$ $⟨ g ⟩ = {g^{0}, g^{1}, ..., g^{i - 1}}$ $I t i s n o t ha r d t o v er i f y t ha t$ \langle g \rangle $i s a s u b g ro u p o f$ \mathbb{G} $o f or d er$ i $an d i s t h u ss ai d t o b e * g e n er a t e d * b y$ g $. T h e in t e g er$ i $i s a l soso m e t im ess im pl yre f erre d t o a s t h eor d ero f t h ee l e m e n t$ g.

There are some interesting properties of such elements.

Lemma

For any element g $o f or d er$ i $in t h e f ini t e g ro u p$ \mathbb{G} $, i t h o l d s t ha t$ g^x = g^y $i f an d o n l y i f$ x = y \mod i.

Proof

TODO

Lemma

The order i $o f an ye l e m e n t$ g $ina f ini t e g ro u p$ \mathbb{G} $, m u s t b e a f a c t oro f t h e g ro u p or d er, i . e .$ i | m $, w h ere$ m $i s t h eor d ero f$ \mathbb{G}.

Proof

TODO

Cyclic Groups

A group \mathbb{G} $i sc a ll e d * cyc l i c * i f a ll o f i t se l e m e n t sc anb eo b t ain e d b y a ppl y in g t h e g ro u p o p er a t i o n re p e t i t e v e l y t o * o n e * o f i t se l e m e n t s . < / d i v >< / d i v > T h e g ro u p$ \mathbb{G} $i sc a ll e d * cyc l i c *, i f t h ere i s an e l e m e n t$ g \in \mathbb{G} $o f or d er$ |\mathbb{G}| $. S u c han e l e m e n t i sc a ll e d a * g e n er a t or * o f$ \mathbb{G} $. T h ere f ore, an ye l e m e n t$ h \in \mathbb{G} $i se q u a lt o$ g^x $f orso m e$ x \in {0,1,..., |\mathbb{G}| -1} $- t h e g ro u p$ \langle g \rangle $ha s$ |\mathbb{G}| $e l e m e n t s an d so d oes t h e g ro u p$ |\mathbb{G}| $an d s in ce$ \langle g \rangle $i s a s u b g ro u p o f$ \mathbb{G}, then they must contain the exact same elements.

Cyclic groups have some interesting properties.

Theorem: Prime Order

Any group \mathbb{G} $w i t ha p r im eor d er$ p is cyclic and all of its elements, except for the identity, are its generators.

Proof

The group order p $* m u s t * b e d i v i s ib l e b y t h eor d er$ i $o f an ye l e m e n t an d so$ i = p $or$ i = 1 $. O n l y t h e i d e n t i t ye l e m e n t ha sor d er$ 1 $an d so a llt h eo t h ere l e m e n t s m u s t b eo f or d er$ p $an d a re t h ere f ore g e n er a t orso f t h e g ro u p . < / d i v >< / d e t ai l s > A nimm e d ia t ecoro ll a ryo f t hi s t h eore mi s t ha tt h e g ro u p$ \mathbb{Z}_p^* $, w h ere$ p $i sso m e p r im e n u mb er, i s a cyc l i c g ro u p o f or d er$ p-1$.

The Cyberclopaedia